package array;

import java.util.*;

/**
 * 数组
 */
public class Solution {

    /**
     * 27. 移除元素
     * 快慢指针
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for(int fast = 0; fast < nums.length; fast++){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }

    /**
     * 704. 二分查找
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 977. 有序数组的平方
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1, index = nums.length - 1;
        int[] result = new int[nums.length];
        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];

            if (leftSquare > rightSquare) {
                result[index] = leftSquare;
                left++;
            } else {
                result[index] = rightSquare;
                right--;
            }
            index--;
        }
        return result;
    }

    /**
     * 209. 长度最小的子数组
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums){
        int left = 0, sum = 0, result = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        return result == Integer.MAX_VALUE ? 0 : result;
    }

    /**
     * 59. 螺旋矩阵 II
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        int count = 1;
        for (int i = 0; i < n / 2; i++) {

            for (int j = left; j < right; j++) {
                result[top][j] = count++;
            }

            for (int j = top; j < bottom; j++) {
                result[j][right] = count++;
            }

            for (int j = right; j > left; j--) {
                result[bottom][j] = count++;
            }

            for (int j = bottom; j > top; j--) {
                result[j][left] = count++;
            }
            left++;
            right--;
            bottom--;
            top++;
        }
        if (n % 2 == 1) {
            result[n / 2][n / 2] = count;
        }
        return result;
    }

    /**
     * 54. 螺旋矩阵
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        List<Integer> result = new ArrayList<>();
        while(left < right && top < bottom) {

            for (int j = left; j < right; j++) {
                result.add(matrix[top][j]);
            }

            for (int j = top; j < bottom; j++) {
                result.add(matrix[j][right]);
            }

            for (int j = right; j > left; j--) {
                result.add(matrix[bottom][j]);
            }

            for (int j = bottom; j > top; j--) {
                result.add(matrix[j][left]);
            }
            left++;
            right--;
            top++;
            bottom--;
        }

        if (left == right && top == bottom) {
            result.add(matrix[top][left]);
        } else if (left == right) {
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][left]);
            }
        } else if (top == bottom) {
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
        }

        return result;
    }

    /**
     * 3. 无重复字符的最长子串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        char[] array = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int left = 0, right = 0, result = 0;

        while (right < array.length) {
            if (!set.contains(array[right])) {
                result = Math.max(result, right - left + 1);
                set.add(array[right]);
                right++;
            } else {
                set.remove(array[left]);
                left++;
            }
        }

        return result;
    }
}
